/*
 * GoPosition.java
 *
 * Created on August 19, 2007, 11:00 AM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package edu.psu.bd.math.grooms;

import java.awt.Container;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Enumeration;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import javax.swing.ProgressMonitor;
import javax.swing.tree.DefaultMutableTreeNode;
import javax.swing.tree.DefaultTreeModel;
import javax.swing.tree.TreeNode;
import org.cgsuite.AbstractShortGame;
import org.cgsuite.CanonicalGame;
import org.cgsuite.ShortGame;
import org.cgsuite.plugin.GridEditable;
import org.cgsuite.util.CacheInput;
import org.cgsuite.util.CacheOutput;
import org.cgsuite.util.Cacheable;
import org.cgsuite.util.Grid;

/**
 *
 * @author joe
 */
public final class GoRoom extends DefaultMutableTreeNode
        implements ShortGame, GridEditable{
    
    public static final int EMPTY = 0;
    public static final int BLACK_STONE = 1;
    public static final int WHITE_STONE = 2;
    public static final int MAX_LIBERTIES = 4;
    
    private final Grid grid;

    public Grid getGrid(){
        return grid.clone();
    }
    
    public GoRoom(Grid g) {
        grid = g;
    }
    
    public int getLastColor() {
        GoRoom parent = (GoRoom) this.getParent();
        if (parent == null)
            return EMPTY;
        if (this.getCount(WHITE_STONE) > parent.getCount(WHITE_STONE))
            return WHITE_STONE;
        if (this.getCount(BLACK_STONE) > parent.getCount(BLACK_STONE))
            return BLACK_STONE;
        throw new IllegalArgumentException();
    }
    
    public GoRoom getRoot() {
        return (GoRoom) super.getRoot();
    }
    
    private void setImmortal() {
    
        Grid f = grid;
        Grid r = new org.cgsuite.util.Grid(
                f.getNumRows(),
                f.getNumColumns(),
                Grid.BitsPerEntry.ONE);
        for (int row = 0;row<f.getNumRows();row++) {
            for (int col = 0;col<f.getNumColumns();col++) {
                if (f.getAt(row,col)!=EMPTY) {
                    r.putAt(row,col,1);
                }
            }
        }
        setUserObject(r);
    }
    private Grid getImmortal() {
        Grid r = (Grid) getRoot().getUserObject();
        return r;
    }
    
    private int getLiberties(int row, int col) {
        
        int count = 0;
        for (org.cgsuite.util.Grid.Direction d :
            org.cgsuite.util.Grid.Direction.ORTHOGONALS) {
                
                if (grid.isValidShift(row,col,d,1)){
                    if (grid.getAt(
                            row + d.rowShift(1),
                            col + d.columnShift(1))
                            == EMPTY) {
                        count++;
                        
                    }
                    
                    
                    
                }
                
            }
            return count;
    }
    
    public int getCount(int value) {
        int count = 0;
        for (int row = 0; row < grid.getNumRows(); row++) {
            for (int col = 0; col < grid.getNumColumns(); col++) {
                if (grid.getAt(row,col) == value) {
                    count++;
                }
            }
        }
        return count;
    }
    
    private int distanceTo(int row, int col, int value) {
        int count = 1;
        while (count <= Algorithms.manhattanDistance(0,0,
                grid.getNumColumns()-1,
                grid.getNumRows()-1)) {
            for (int r = 0; r < grid.getNumRows(); r++) {
                for (int c = 0; c < grid.getNumColumns(); c++) {
                    if ((Algorithms.manhattanDistance(row,col,r,c) == count)
                    && (grid.getAt(r,c) == value)) {
                        return count;
                    }
                }
            }
            count ++;
        }
        return 0;
        
        
    }
    
    public org.cgsuite.util.Grid[] getGrids() {
        
        
        int size = getCount(EMPTY);
        
        
        
        org.cgsuite.util.Grid blackList = new org.cgsuite.util.Grid(
                size,MAX_LIBERTIES);
        org.cgsuite.util.Grid whiteList = new org.cgsuite.util.Grid(
                size,MAX_LIBERTIES);
        
        
        
        for (int row = 0; row < grid.getNumRows(); row++) {
            for (int col = 0; col < grid.getNumColumns(); col++) {
                if (grid.getAt(row,col) == EMPTY) {
                    int liberties = getLiberties(row,col);
                    if (liberties != 0) {
                        
                        
                        Algorithms.incrementAt
                                (blackList,distanceTo(row,col,BLACK_STONE)-1,
                                liberties-1 );
                        
                        Algorithms.incrementAt
                                (whiteList,distanceTo(row,col,WHITE_STONE)-1,
                                liberties-1);
                        
                        
                        
                    }
                }
            }
        }
        
        
        
        
        whiteList = Algorithms.trimGrid(whiteList);
        blackList = Algorithms.trimGrid(blackList);
        
        org.cgsuite.util.Grid[] result = new org.cgsuite.util.Grid[2];
        result [0] = blackList;
        result [1] = whiteList;
        return result;
    }
    
    private Collection<? extends ShortGame> getOptions(int value) {
        Collection<GoRoom> c = new ArrayList<GoRoom>();
        for (Enumeration e = this.children();
        e.hasMoreElements();) {
            GoRoom gr = (GoRoom) e.nextElement();
            if (gr.getLastColor() == value) {
                c.add(gr);
            }
        }
        if (!c.isEmpty())
            
            return c;
        Collection<CanonicalGame> d = new ArrayList<CanonicalGame> ();
        GoRoom root = this.getRoot();
        GoRoom next = (GoRoom) this.getParent();
        int score = 0;
        while (root != next) {
            score += next.getCapturedMultiplier()
            * next.getNumCaptured();
            next = (GoRoom) next.getParent();
        }
        if (score > 0 && value == BLACK_STONE) {
            d.add(new CanonicalGame(score -1));
            return d;
        }
        if (score < 0 && value == WHITE_STONE) {
            d.add(new CanonicalGame(score+1));
            return d;
        }
        return c;
    }
    
    public Collection<? extends ShortGame> getLeftOptions() {
        return getOptions(BLACK_STONE);
    }
    
    public Collection<? extends ShortGame> getRightOptions()  {
        return getOptions(WHITE_STONE);
    }
    
    public ShortGame getInverse() {
        return this.solve().getInverse();
    }
    
    public static int getInverse(int value) {
        switch (value) {
            case BLACK_STONE:
                return WHITE_STONE;
            case WHITE_STONE:
                return BLACK_STONE;
            case EMPTY:
                return EMPTY;
                
        }
        throw new IllegalArgumentException();
    }
    

    public void initialize()
    throws KoException, InterruptedException {
        this.setImmortal();
        
        while (growTree()){
        
        }

        this.setUserObject(null);
        
        LinkedList<GoRoom> list = new LinkedList<GoRoom>();
        for(Enumeration e = this.breadthFirstEnumeration();
        e.hasMoreElements();){
            list.addFirst((GoRoom)e.nextElement());
        }
        for(GoRoom gr : list) {
            if (Thread.interrupted())
            {
                throw new InterruptedException();
            }
            gr.solve();
        }
    }
    
    public boolean growTree() throws KoException, InterruptedException {
        
        boolean isChanged = false;
        
        Collection<GoRoom> leaf = new ArrayList<GoRoom>();
        for (Enumeration e = this.depthFirstEnumeration();
        e.hasMoreElements();) {
            GoRoom gr = (GoRoom) e.nextElement();
            if (gr.isLeaf()){
                leaf.add(gr);
                
            }
        }
        
        for (GoRoom gr:leaf){
            for (int r = 0; r < grid.getNumRows(); r++) {
                for (int c = 0; c < grid.getNumColumns(); c++) {
                    if (gr.processMove(r,c,WHITE_STONE))
                        isChanged = true;
                    if (gr.processMove(r,c,BLACK_STONE))
                        isChanged = true;
                    
                }
            }
        }
        return isChanged;
    }
    
    private boolean processMove(
            int row,
            int col,
            int value) throws KoException, InterruptedException {
        if (Thread.interrupted()){
            throw new InterruptedException();
        }
        
        Grid result = grid.clone();
        Grid immortal = this.getImmortal();
        
        // Is the point already occupied?
        if (result.getAt(row,col) != EMPTY) {
            return false;
        }
        
        
        // Is the move suicide?
        boolean suicide = true;
        for (org.cgsuite.util.Grid.Direction d:
            org.cgsuite.util.Grid.Direction.ORTHOGONALS) {
                if (!result.isValidShift(row,col,d,1))
                    continue;
                
                if (result.getAt(row+d.rowShift(1),
                        col+d.columnShift(1)) == EMPTY) {
                    // if any neighbor is VACANT, suicide = false
                    suicide = false;
                }else if (result.getAt(row+d.rowShift(1),
                        col+d.columnShift(1)) == value) {
                    // if any neighbor is an ally
                    // that isn't in atari
                    if (!Algorithms.getChain(result,row+d.rowShift(1),
                            col+d.columnShift(1)).inAtari(immortal)) {
                        suicide = false;
                    }
                }else if (result.getAt(row+d.rowShift(1),
                        col+d.columnShift(1)) == getInverse(value)) {
                    // if any neighbor is an enemy
                    // and that enemy is in atari
                    
                    Chain enemy = Algorithms.getChain(result,row+d.rowShift(1),
                            col+d.columnShift(1));
                    if (enemy.inAtari(immortal)) {
                        suicide = false;
                        
                        // remove the enemy stones from the board
                        Grid s = enemy.getStones();
                        Algorithms.removeAll(result, s);
                        
                        
                    }
                }
            }
            
            if (suicide) {
                return false;
            }
            
            
            koTest(row,col,value);
            
            // If the point is not occupied, the move is not ko, and not suicide
            // it is a legal move.
            result.putAt(row,col,value);
            
            GoRoom child = new GoRoom(result);
            this.add(child);
            
 
            
            return true;
            
    }
    
    private int getCapturedMultiplier() {
        switch (this.getLastColor()) {
            case WHITE_STONE:
                return -1;
            case BLACK_STONE:
                return 1;
            case EMPTY:
                return 0;
                
        }
        throw new IllegalArgumentException();
    }
    
    private int getNumCaptured() {
        GoRoom parent = (GoRoom) getParent();
        if (parent == null)
            return 0;
        int myColor = this.getLastColor();
        int otherColor = GoRoom.getInverse(myColor);
        return parent.getCount(otherColor) - this.getCount(otherColor);
    }
    
    
    private void koTest(int row, int col, int value) throws KoException {
        // If this move captured exactly one stone, that stone is the new ko point
        if (this.getNumCaptured() == 1) {
            GoRoom parent = (GoRoom) this.getParent();
            
            if (parent == null)
                return;
            
            if (parent.getGrid().getAt(row,col) == value)
                throw new KoException(grid);
            
        }
        
    }
    
    
    
    public CanonicalGame solve() {
        
        Collection<? extends ShortGame> l = this.getLeftOptions();
        Collection<? extends ShortGame> r = this.getRightOptions();
        Collection<CanonicalGame> lc = new ArrayList<CanonicalGame> ();
        Collection<CanonicalGame> rc = new ArrayList<CanonicalGame> ();
        if (getUserObject() != null)
            return ((GoRoomUserObject) getUserObject()).getValue();
        
        
        
        for (ShortGame s : l) {
            lc.add(s.solve());
        }
        for (ShortGame s : r) {
            rc.add(s.solve());
        }
        CanonicalGame value = new CanonicalGame(lc,rc);
        this.setUserObject(new GoRoomUserObject(value));
        return solve();
        
    }

    
}